# -*- coding: utf-8 -*-

"""稳定匹配算法，就是一个社会学的问题，最常见的算法就是稳定婚姻算法。
如果让所有单身男士先发起追求，一轮只能追求一个，并且每轮按喜欢程度依次往后追求；
在一轮中，女士将所有的追求者和前面轮中匹配的男士放到一起，按中意程度进行比较，是为择偶，这个择偶决定哪个男士成为匹配者，剩下的男士变为单身汉。
这个稳定匹配算法，就成为了这样的场景，如果某个男士想跟比现任匹配更喜欢的女士匹配，那么他肯定之前追求过这个女士，但是被那位女士拒绝了，所以就形成稳定匹配；
同理，如果某个女士想给比现任匹配更喜欢的男士匹配，但是按流程，她的意中人没有追求过她，如果追求过，她就会跟意中人在一起了，所以从女士角度出发这个匹配关系也是稳定的。
大白话就是稳定匹配后，男的撬不动，女的也撬不动。"""

class GaleShapley():
    def __init__(self):
        pass

    def stable_marriage(self, Vm, Vw, E, g):
        """input: 有向带权偶图
        @Vm:= [Jack, Bob]    # 男士
        @Vw:= [Alice, Luna]    # 女士
        @E:= {(Jack, Alice), (Bob, Luna)}    # 男士对女士有好感 或 女士对男士有好感
        @g:= f: Vm*Vn -> Number    # 好感度打分
        --------------------------------------
        output: 男女姓名的二元组集合
        {(Jack, Alice), (Bob, Luna)}
        """
        chase_like_order, match_like_order = [[] for _ in Vm], [[] for _ in Vw]
        for r in E:
            likeV = g(r)
            try:
                chase = Vm.index(r[0])
                matq = Vw.index(r[1])
                chase_like_order[chase].append((likeV, matq))
            except ValueError:
                matq = Vw.index(r[0])
                chase = Vm.index(r[1])
                match_like_order[matq].append((likeV, chase))

        for chase, like_order in zip(range(len(Vm)), chase_like_order):
            like_order.sort()
            like_order.reverse()
            chase_like_order[chase] = tuple([like[1] for like in like_order])

        for matq, like_order in zip(range(len(Vw)), match_like_order):
            like_order.sort()
            like_order.reverse()
            match_like_order[matq] = tuple([like[1] for like in like_order])

        chase_like_order, match_like_order = tuple(chase_like_order), tuple(match_like_order)

        for chase, like_order in zip(Vm, chase_like_order):
            print(chase, [Vw[matq] for matq in like_order], sep=': ')
        for matq, like_order in zip(Vw, match_like_order):
            print(matq, [Vm[chase] for chase in like_order], sep=': ')

        # --------------------------------------------------------
        rs = self.stable_match(chase_like_order, match_like_order)
        # --------------------------------------------------------

        output = set()
        for women, man in zip(range(len(Vw)), rs):
            try:
                output.add((Vm[man], Vw[women]))
            except TypeError:    # 某位男士没有匹配到 Vm[None]
                continue
        return output

    def stable_match(self, chase_like_order, match_like_order):
        """将具体的男女姓名抽象为数组的下标号，代表顶点，这样核心过程方便向其他场景兼容。
        input:
        @chase_like_order:= tuple(tuple(w1, w4, w2), tuple(...), tuple(...), ...)    # 追求者的中意顺序，用于单身状态时每轮按顺序发起追求。固定值的好感度已经不重要了，重要的是按好感度要排序出来
        @match_like_order:= tuple(tuple(m6, w3, w5), tuple(...), tuple(...), ...)    # 择偶者的中意顺序，用于每轮对所有的倾慕者进行比较择偶。实际上用字典表在效率上更好，但是为了直观好理解，跟男士一样用元组或列表
        --------------------------------------
        process:
        @active_chase:= set{m1, m2, m3, ...}    # 可以出击的追求者，单身男（女）士的集合
        @chase_next = [pi, pj, pk, ...]    # 追求者可以对第几个中意的发起追求，意中人序列中的序号
        @match_state = [{m1}, {m3}, {m4}, ...]    # 择偶者的状态，各女（男）士的追求者标号
        --------------------------------------
        output:
        [m1, m3, m4, ...]    # 各择偶者最终选择的匹配对象
        """
        active_chase = set(range(len(chase_like_order)))
        chase_next = [0 if like_order else None for like_order in chase_like_order]
        match_state = [set() for _ in match_like_order]

        while True:
            # print('.....................')
            # print(active_chase)
            # print(chase_next)
            count = 0

            # 单身追求者向当前意中人发起追求
            for chase in active_chase:
                p = chase_next[chase]    # 该向第几个意中人发起追求
                if p is None:    # 如果没有意中人，便不发起追求
                    continue
                try:
                    matq = chase_like_order[chase][p]    # 从喜欢顺序中选择意中人
                except IndexError:    # 后面已经没有意中人可以发起追求了
                    continue
                match_state[matq].add(chase)    # 找到意中人，发起追求
                chase_next[chase] += 1    # 下一次该追求下一位意中人
                count += 1

            if not count:    # 如果所有单身人士都没有发起追求，或者无单身人士了，则整个匹配过程结束
                break

            # 择偶者对所有追求者进行选择匹配
            for matq in range(len(match_state)):
                like_order = match_like_order[matq]    # 择偶者的喜欢顺序
                favc, foremost = None, float('inf')
                for chase in match_state[matq]:    # 遍历择偶者的所有追求者，找出最中意的
                    try:
                        loc = like_order.index(chase)
                    except ValueError:    # 这个追求者不在择偶者的中意名单中
                        continue
                    if loc < foremost:
                        favc, foremost = chase, loc

                if favc is None:
                    continue

                active_chase.discard(favc)    # 更新下一轮可主动发起追求的人
                for chase in match_state[matq]:
                    if chase != favc:
                        active_chase.add(chase)

                match_state[matq].clear()
                match_state[matq].add(favc)    # 择偶状态取匹配者，唯一一个

            # print(match_state)

        return [chase.pop() if chase else None for chase in match_state]


if __name__ == '__main__':
    Vm = ['Alex', 'Chris', 'David', 'Bob']
    Vw = ['Ada', 'Becky', 'Cindy', 'Diana']
    E = {
        ('Alex', 'Ada'),('Alex', 'Becky'),('Alex', 'Cindy'),('Alex', 'Diana'),
        ('Chris', 'Ada'),('Chris', 'Becky'),('Chris', 'Cindy'),('Chris', 'Diana'),
        ('David', 'Ada'),('David', 'Becky'),('David', 'Cindy'),('David', 'Diana'),
        ('Bob', 'Ada'),('Bob', 'Becky'),('Bob', 'Cindy'),('Bob', 'Diana'),

        ('Ada', 'Alex'),('Ada', 'Chris'),('Ada', 'David'),('Ada', 'Bob'),
        ('Becky', 'Alex'),('Becky', 'Chris'),('Becky', 'David'),('Becky', 'Bob'),
        ('Cindy', 'Alex'),('Cindy', 'Chris'),('Cindy', 'David'),('Cindy', 'Bob'),
        ('Diana', 'Alex'),('Diana', 'Chris'),('Diana', 'David'),('Diana', 'Bob')
    }
    def g(r):
        like = {
            ('Alex', 'Ada'): 4,('Alex', 'Becky'): 1,('Alex', 'Cindy'): 2,('Alex', 'Diana'): 3,
            ('Chris', 'Ada'): 1,('Chris', 'Becky'): 4,('Chris', 'Cindy'): 2,('Chris', 'Diana'): 3,
            ('David', 'Ada'): 3,('David', 'Becky'): 2,('David', 'Cindy'): 4,('David', 'Diana'): 1,
            ('Bob', 'Ada'): 4,('Bob', 'Becky'): 3,('Bob', 'Cindy'): 2,('Bob', 'Diana'): 1,
            
            ('Ada', 'Alex'): 3,('Ada', 'Chris'): 4,('Ada', 'David'): 1,('Ada', 'Bob'): 2,
            ('Becky', 'Alex'): 4,('Becky', 'Chris'): 2,('Becky', 'David'): 3,('Becky', 'Bob'): 1,
            ('Cindy', 'Alex'): 1,('Cindy', 'Chris'): 2,('Cindy', 'David'): 3,('Cindy', 'Bob'): 4,
            ('Diana', 'Alex'): 2,('Diana', 'Chris'): 1,('Diana', 'David'): 4,('Diana', 'Bob'): 3
        }
        return like[r]

    gs = GaleShapley()
    rs = gs.stable_marriage(Vm, Vw, E, g)
    print(rs)
